With the rapid development of the Internet, an interface rate of a core router used for interconnection of backbone networks has reached 100 Gbps, and such a rate requires that the core router has a routing lookup rate as high as millions of times per second while supporting a routing table having a large capacity. Internet Protocol (IP) lookup requires acquisition of a longest prefix matching, and a software lookup method is no longer applicable as required by high speed lookup. In recent years, researchers have proposed many hardware lookup methods to improve lookup efficiency, prevailed by a Trie tree structure and a Ternary Content Addressable Memory (TCAM).
The Trie tree structure, which is the most widely used tree structure, is easy to implement a pipeline operation on hardware and beneficial to improvement of the throughput rate of routing lookup. However, the Trie tree structure has a certain limitation. A common Trie tree structure has a large number of pipeline levels, which results in a relatively long lookup delay. The number of pipeline levels may be greatly reduced by applying a routing lookup design with a multi-bit Trie tree structure, but a great amount of additional memory consumption will be caused, and such additional memory consumption is related to distribution of prefixes of a routing table, thus resulting in relatively large fluctuation of a routing table capacity of a routing lookup hardware design based on a multi-bit Trie tree, and a relatively low utilization rate of a memory space in worse routing distribution.
At present, there is no effective solution to solve the problem that a routing lookup solution in the related art has large memory consumption and affects routing lookup efficiency.